The present invention relates to pattern recognition and specifically relates to devices and methods relating to surfaces having a coding pattern available for analysis.
In many contexts, it is desirable to be able to determine an absolute position on a surface. One example is in the digitization of drawings. Another example is when it is desirable to produce an electronic version of handwritten information. In these and other contexts in which position determination is performed, it is often desirable to use a computer program in cooperation with an input device to carry out calculations related to position determination.
U.S. Pat. No. 5,852,434, for example, discloses a device for determining an absolute position. The device includes a writing surface having a position-coding pattern used to determine X/Y coordinates, a detector for detecting the position-coding pattern and a processor for determining the position of the detector in relation to the writing surface based on the detected position-coding pattern. The device makes it possible for a user to input handwritten and hand-drawn information into a computer at the same time as the information is written/drawn on the writing surface.
A number of examples of position coding are given in U.S. Pat. No. 5,852,434. The first example shows symbols built up of three concentric circles, with the outermost circle representing the x-coordinate and the middle one representing the y-coordinate. The two outermost circles are further divided into 16 parts that specify different numbers depending on their fill pattern. Each pair of x/y coordinates is coded with a complex symbol having a special appearance. In the second disclosed example, the coordinates at every point on the writing surface are identified with the aid of a bar code, a bar code for the x-coordinate being specified above a bar code for the y-coordinate.
Devices in the prior art used for this type of detection are generally constructed to register four symbols at the same time ensuring a reliably capture of at least one symbol in its totality. This capture is necessary for the device to perform the position determination.
The prior art summarized above does not disclose, for example, a computer program used in cooperation with an input device to perform calculations related to the position determination because generally only position information is processed. The prior art has further shortcomings because the patterns used are built up of complex symbols, the information content of that indicates the actual positions. The smaller these symbols are the more difficult it becomes to produce the patterned writing surface, while increasing the risk of erroneous position determinations. On the other hand, the use of larger the symbols decreases the position resolution.
In Applicant""s International Patent Application WO 00/73983, which was filed on Oct. 1, 1999 and which was not publicly available when the present application was filed and therefore does not constitute prior art, a position coding pattern is described. Moreover reference is also made to PCT/SE00/01895 and WO 01/16691, the contents of which are included by reference.
A solution therefore is required to overcome the deficiencies of the prior art.
Systems and methods consistent with the present invention may have coding patterns with a number of spatial levels and utilizing the spatial levels.
It is an object of the present invention to remedy the abovementioned deficiencies of prior art completely or partially.
More specifically, the invention relates to a product that has a surface that is provided with a coding pattern that comprises symbols that have at least two different values. The invention is characterized in that each symbol comprises a raster point and at least one marking, that the raster point is included in a raster which extends over the surface; that the value of each symbol is indicated by the location of said marking in relation to a raster point and that at least one marking comprises marking information.
In prior art, each position is coded with a complex symbol, the complete information content of which is needed for specifying position information. According to the invention, instead, a symbol is used the value of which is specified by the location of a marking in relation to a raster point. There is thus one type of symbol for each value. A device which will carry out the position determination therefore only needs to detect the occurrence of one marking. Moreover, a position-determining device according to the invention can distinguish between different markings and thereby acquire further information related to, for example, the position in question. This further marking information can advantageously vary depending on the position that is determined.
The design of the symbol according to the invention also entails that a surface which is provided with a coding pattern according to the invention becomes more aesthetically pleasing.
Furthermore, a large distance between the markings in relation to the position-information density is made possible, which has the result that the coding becomes less sensitive to movement blur.
The symbols described above can be used for coding any type of information but are advantageously used for coding positions and position-related further information via the markings of the symbols. As mentioned, in prior art each position is coded with a single symbol that therefore must be rather complex. According to the invention, on the other hand, each position can be coded with a plurality of symbols. Each individual symbol can thus be made less complex and thus simpler to detect with higher reliability.
According to the invention, the position information and position-related information are separated in that the markings of the symbols contain different types of information depending on which spatial resolution is taken into consideration. In a first spatial resolution level, the markings of the symbols are only used for specifying position information. By taking into consideration further spatial resolution levels that are higher than the first one, the further information can be coded and retrieved from the markings. An obvious advantage of this separation of information into different spatial resolution levels is that, even if reading the markings entails loss of detail information, at least the information which has been stored with the lowest spatial resolution, i.e. the existence of the markings itself, can be utilized. This will also prove to be advantageous when considering reading devices and their capability of reading information of different spatial resolution, as will be discussed further below.
In prior art, each position is coded with a symbol that is xe2x80x9cisolatedxe2x80x9d from symbols of the surrounding positions. The position resolution is thus limited by the surface occupied by the symbol of a position. The position-coding pattern according to the invention can be built up in corresponding manner, each position being coded by an xe2x80x9cisolatedxe2x80x9d group of symbols. In a preferred embodiment of the invention, however, each symbol contributes to the coding of more than one position. In this manner, a xe2x80x9cfloatingxe2x80x9d transition between different positions is obtained. In other words, each position is coded partly by the same symbols as the adjoining positions. The floating coding is advantageous since it makes it possible to increase the position resolution. Furthermore, it is possible to reduce the relationship between, on the one hand, the number of symbols which a position-determining device must register in order to be able to carry out a position determination reliably and, on the other hand, the number of symbols which code a position.
In a preferred embodiment, each symbol contributes to the coding of both a first and a second position coordinate. Thus, different symbols are not needed for the different coordinates, which make the position code simpler and the position resolution better. The coordinate system can be suitably Cartesian but other types of coordinate systems are also conceivable.
Furthermore, the value of each symbol can be advantageously translatable into at least a first digit which is used for coding the first coordinate, and at least a second digit which is used for coding the second coordinate, the symbols in the position-coding pattern together representing a first position code for the first coordinate and a second position code for the second coordinate. The two coordinates can then be coded independently of one another, which makes the coding simpler when the coding is xe2x80x9cfloatingxe2x80x9d. Preferably, the value of the symbol is represented in a binary manner, a first bit being used for the coding of a first coordinate and a second bit for the coding of a second coordinate.
The position-coding pattern is advantageously based on a first cyclic, preferably binary, number series which has the characteristic that no sequence with a first predetermined number of digits appears more than once in the number series. Due to the fact that the position-coding pattern is built up in this manner, it will contain inherent information about the positions so that the coordinates can be calculated according to predetermined rules. This is advantageous in that it means that the decoding of the position-coding pattern can be implemented in an efficient manner in, for example, software. Besides, it will be much simpler to produce the position-coding pattern in this way compared with trying to randomly generate an unambiguous position-coding pattern of a floating type.
In one embodiment, the product can comprise a plurality of writing surfaces each of which comprises the position-coding pattern with the further marking information coded in a number of markings. For example, the product can consist of a notepad with a plurality of sheets, such as maps, forms, blanks etc. The position-coding patterns then differ for the various writing surfaces by the sequence in the cyclic number series with which a predetermined column or row begins. The xe2x80x9csamexe2x80x9d pattern can thus be used for a plurality of writing surfaces which can be separated or integrated with one another by allowing, for example, the first column to begin at different positions in the number series.
Considering the further marking information, this can be seen as providing an extension of the cyclic number series with the advantage of providing an even larger available area, which can be provided with a unique coding pattern.
The position-coding pattern can be implemented with any parameter whatever that can be used for producing symbols of the above-mentioned type which can be detected by a detector. The parameter can be electric or chemical or of another type. However, the position-coding pattern is preferably optically readable which makes it simpler to apply it to the surface. The pattern should thus be able to reflect or absorb light but the light does not need to lie within the visible range.
The raster and/or the raster points can be implemented on the surface. In a preferred embodiment, however, the raster and the raster points are virtual. Thus, the raster is not marked on the surface at all but only constitutes an imaginary raster which forms the base of the coding but which can be located on the basis of the location of the markings.
The products described above can be any products whatever that have a surface with a coding pattern. They can be used for a large number of different applications. For example, they can be used for continuously registering the position of a pen which is conducted over the writing surface where the further position-related marking information, for example, contains direct information about how the written text is to be reproduced, for example on a computer screen. Further examples comprise a map with a printed pattern according to the invention, whereby, for example, the further information in the markings can contain information relating, for example, levels of elevation. They can also be used in determining the position of a tool, an instrument or the like. They can also be used as a mouse pad. A person skilled in the art can think of many other applications.
According to yet another aspect of the invention, it relates to a computer program for determining the position of a partial surface on a surface, which is provided with a position-coding pattern which comprises a plurality of symbols, on the basis of an image of the partial surface, each symbol comprising a raster point and at least one marking, the computer program being stored on a storage medium which can be read by a computer and which comprises instructions for causing the computer to locate a predetermined plurality of symbols in the image, to determine the value of each of the said predetermined plurality of symbols, to separate the position-coding pattern in the image into a first position code for a first coordinate and a second position code for a second coordinate by translating the value of each symbol into at least a first digit for the first position code and at least a second digit for the second position code, and to calculate the first coordinate with the aid of the first position code and the second coordinate with the aid of the second position code. Moreover, the locating of at least one marking is carried out, which comprises marking information, after which this is interpreted.
The computer programs can be used together with prior-art position-determining devices. They can be installed in a separate computer to which images of the position-coding pattern are sent, or in the actual device that registers the position-coding pattern.
According to another aspect of the invention, it relates to a device for position determination, comprising a sensor for producing an image of a partial surface on a surface and image-processing devices which are arranged to decode a position-coding pattern on a product the surface being a surface on the product, which surface is provided with the position-coding pattern.
More specifically, systems and methods consistent with the present invention may employ a principle surface with a coding pattern that may include symbols having at least two different values. Each symbol may include a raster point and at least one marking. The raster point may be included in a raster extending over the surface, and the value of each symbol may be indicated by the location of the marking in relation to a raster point. The marking may include marking information.
Another aspect of the invention, may employ a program stored on a computer-readable medium for determining the position of a partial surface on a surface having a position-coding pattern that includes a plurality of symbols, with each symbol including a raster point and at least one marking. The program may include instructions for locating a predetermined plurality of symbols in an image of the partial surface, determining the value of each said predetermined plurality of symbols, separating the position-coding pattern into a first position code for a first coordinate of the partial surface and a second position code for a second coordinate of the partial surface by translating the value of each symbol into at least a first digit for the first position code and at least a second digit for the second position code. The program instruction may further calculate the first coordinate using the first position code and the second coordinate using the second position code, calculate the value of each symbol by determining the location of each marking in relation to the raster point; locate at least one marking having marking information; and interpret the marking information.
In another aspect, a system according to the invention may include a sensor configured to produce an image of a partial surface of a plurality of partial surfaces on a principle surface, the partial surface including a position-coding pattern. The system further may include an image-processing element configured to locate a predetermined plurality of symbols in the image, with each symbol including at least one marking. The image processing element may also be configured to determine the value of each of the predetermined plurality of symbols, separate the position-coding pattern in the image into a first position code for a first coordinate for the partial surface and into a second position code for a second coordinate for the partial surface by translating the value of each symbol into at least a first digit for the first code and at least a second digit for the second code, calculate the first coordinate using the first position code and the second coordinate using the second position code, locate at least one marking which comprises marking information and interpret the marking information. In this aspect, the image-processing element may be in wireless, optical, or direct communication with the sensor.
The capability of interpreting the further information at different spatial resolutions will prove very advantageous in a commercial sense. Devices for interpreting the position information and further information of any spatial resolution are envisaged, but also devices capable of interpreting only position information and further information at only one other spatial resolution (or even no other spatial resolution than that of the position information). Such separation of devices into different levels of capability may be utilized commercially in that several generations of devices may be developed, each being capable of interpreting further information at further spatial resolutions. Backward compatibility will be inherent in that the capability for early generation devices capable of interpreting information at, e.g., one or two spatial resolutions will also be able to interpret the information of the first one or two spatial resolutions from symbols having information at three or more spatial resolutions.
One general advantage of the present invention is the fact that a number of different spatial resolution levels can be used. Reading devices such as reading pens can be provided with different capacity for reading and decoding position information and marking information. For example, a simple and inexpensive reader can be produced for simply reading the pattern at the lowest spatial resolution level whilst a more advanced and more expensive reader can be produced for reading information at a number of spatial resolution levels.
Additional features and advantages of the invention are set forth in the following description, may be apparent from the description, or may be learned by practicing the invention. The foregoing summarizes only a few aspects of the invention and is not intended to be in any way reflective of the full scope of the invention as claimed. Moreover, both the foregoing general description and the following detailed description are exemplary and explanatory and are intended to provide further explanation of the invention as claimed.